import numpy as np

class TarjansAlgorithm:

    def __init__(self):
        # the number of variables in the problem
        self.size = 0

        # The index of the next variable in the DFS.
        self.index = -1 #int index;
        
        # A stack to keep track of the variables in the current SCC.
        self.S = None   #std::stack<int> S;
        
        # An efficient data structure to track the current contents of the S stack.
        self.sContents = None   #varset sContents;
        
        # A mapping from a variable to its index value.
        self.indices = None #std::vector<int> indices;
         
        # A mapping from a variable to its lowlink value.
        self.lowlink = None #std::vector<int> lowlink;

        # A list of all discovered strongly connected components (cycles).
        self.stronglyConnectedComponents = None #std::vector< std::vector<int> > stronglyConnectedComponents;


    def getSCCs(self, graph):
        self.graph = graph
        self.size = len(graph)

        self.S = list()
        self.sContents = np.zeros(self.size)
        self.indices = np.zeros(self.size)
        self.lowlink = np.zeros(self.size)
        self.stronglyConnectedComponents = list()


        for i in range(self.size):
            self.indices[i] = -1
            self.lowlink[i] = -1

        self.stronglyConnectedComponents.clear()

        # index := 0
        # S := empty
        # for each v in V do
        #   if v.index is undefined
        #     strongconnect(v)
        self.index = 0
        self.S.clear()

        for v in range(self.size):
            if self.indices[v] == -1:
                self.strongconnect(v)

        return self.stronglyConnectedComponents

    def strongconnect(self, v):
        # Set the depth index for v to the smallest unused index
        # v.index := index
        # v.lowlink := index
        # index := index +1
        # S.push(v)

        self.indices[v] = self.index
        self.lowlink[v] = self.index
        self.index += 1
        self.S.append(v)
        self.sContents[v] = 1

        # Consider successors of v

        # for each (v, w) in E
        #   if w.index is undefined
        #     strongconnect(w)
        #     v.lowlink := min(v.lowlink, w.lowlink)
        #   else if w is in S
        #     v.lowlink := min(v.lowlink, w.index)

        for w in range(self.size):
            # in some cases, it seems that v,w should be swapped...?
            if self.graph.getEdge(v, w) == 0:
                continue

            #print("The edge from '{}' to '{}' exists.".format(v, w))

            if self.indices[w] == -1:
                self.strongconnect(w)
                mi = min(self.lowlink[v], self.lowlink[w])
                self.lowlink[v] = mi
            elif self.sContents[w] != 0:
                mi = min(self.lowlink[v], self.indices[w])
                self.lowlink[v] = mi

        # if v is a root node, pop the stack and generate an SCC

        # if v.lowlink = v.index
        # start a new scc
        # do
        #   w = S.pop
        #   add w to current scc
        # until w = v
        # output the current scc

        if self.lowlink[v] == self.indices[v]:
            scc = np.zeros(self.size)

            w = None
            while w != v:
                w = self.S.pop()
                self.sContents[w] = 0
                scc[w] = 1
            # insert at the beginning of the list so that the SCCs
            # come out in topological order
            self.stronglyConnectedComponents.insert(0, scc)

